學習資源

https://labuladong.online/algo/data-structure-basic/rbtree-basic/

學習記錄

今天是學習的第 28 天，主要學習了紅黑樹的平衡：

為什麼需要紅黑樹？

二叉搜索樹（BST）的操作效率取決於樹的高度。在理想的情況下，當樹的結構越平衡時，樹的高度就越接近 log n，這個時候增刪查改的時間複雜度都能維持在 O(log n)。

但是，普通的二叉搜索樹存在一個缺陷：它不會自動維持平衡。在某些極端情況下，例如按照順序插入節點時，二叉搜索樹會退化成一條鏈表，此時樹的高度變成 n，所有操作的時間複雜度都會退化到 O(n)，完全失去了二叉搜索樹的優勢。

什麼是紅黑樹？

紅黑樹是一種經過優化的、能夠自平衡的二叉搜索樹。

通過為每個節點增加一個顏色屬性（紅色或黑色），並遵循一組嚴格的規則，紅黑樹能夠確保在任何時候、任何情況下，樹的高度都能夠保持在 O(log n) 的範圍內，從而保證增刪查改的時間複雜度都是 O(log n)。

在第一張圖中，我們可以看到一個簡單的樹結構：

• 節點 0（灰色）位於左側
• 節點 1（灰色）作為根節點
• 節點 2（紅色）位於右下方
• 節點 3（灰色）位於右上方

這個結構展示了紅黑樹中節點的顏色標記。紅色節點（節點 2）與其他灰色（黑色）節點共同維持著樹的平衡性質。

在第二張圖中，我們看到經過調整後的樹結構：

• 節點 0（灰色）位於最左側
• 節點 1（紅色）成為左子樹的一部分
• 節點 2（灰色）也在左側
• 節點 3（灰色）成為新的根節點
• 節點 4（灰色）位於右側

這兩張圖展示了紅黑樹在插入或刪除節點後，通過旋轉和重新著色來維持平衡的過程。可以觀察到，雖然樹的結構發生了變化，但整體高度依然保持在較低水平，確保了操作效率。

學習總結

• 二叉搜索樹的效率瓶頸：操作效率取決於樹的高度，不平衡的樹會導致性能退化
• 紅黑樹的核心價值：通過自平衡機制，保證在任何情況下都能維持 O(log n) 的時間複雜度